Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Maximum Length of Semi-Decreasing Subarrays

Problem Statement

Given an integer array nums, return the length of the longest semi-decreasing subarray of nums, or 0 if there are no such subarrays.

If the first element is strictly greater than its last element for any array, it is semi-decreasing.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

  • Example 1:

    • Input: nums = [8, 4, 5, 3, 2]
    • Expected Output: 5
    • Justification: The entire array is the largest segment where the first element (8) is greater than the last (2).
  • Example 2:

    • Input: nums = [1, 2, 3, 4, 5]
    • Expected Output: 0
    • Justification: There's no segment where the starting number is greater than the ending number.
  • Example 3:

    • Input: nums = [1, 2, 12, 2, 5, 11, 13]
    • Expected Output: 4
    • Justification: The largest semi-decreasing subarray is [12, 2, 5, 11].

Solution

To solve this problem, we adopt a straightforward yet effective approach by examining all possible contiguous subarrays within the given array to identify those that meet the specific criterion of being semi-decreasing. This means we look for segments where the starting element is strictly greater than the ending element, without imposing restrictions on the sequence's behavior between these two points. Through meticulous iteration, starting from each element and comparing it with subsequent elements, we ensure no potential solution is overlooked.

This exhaustive method, while simple, leverages the power of brute force to methodically parse through the array, ensuring that the maximum length of any such semi-decreasing subarray is captured accurately. By evaluating each segment's starting and ending points against our criteria, we pinpoint the longest segment that fulfills the condition, thus arriving at the solution.

Step-by-step Algorithm

  1. Initialize Variables:

    • Start with a variable maxLength set to 0, which will hold the maximum length of a semi-decreasing subarray found.
    • Use two nested loops with indices i and j to iterate through the array, where i starts from 0 and j starts from i + 1.
  2. Iterate Through the Array:

    • The outer loop runs through each element of the array, treating each element as a potential starting point of a semi-decreasing subarray.
    • The inner loop runs from the next element after i to the end of the array, considering each as a potential end of a semi-decreasing subarray starting at i.
  3. Check for Semi-Decreasing Subarray:

    • Within the inner loop, check if the element at the start of the subarray (index i) is greater than the element at the current end of the subarray (index j). This checks the condition for a subarray being semi-decreasing.
  4. Update Maximum Length:

    • If the condition in step 3 is true, calculate the length of the current subarray (j - i + 1) and compare it with maxLength.
    • Update maxLength if the current subarray's length is greater.
  5. Return Result:

    • After the loops complete, return the value of maxLength, which now contains the length of the longest semi-decreasing subarray found.

Algorithm Walkthrough

Let's consider the Input: nums = [1, 2, 12, 2, 5, 11, 13].

  1. Initialization:

    • maxLength is initialized to 0. This variable will store the length of the longest semi-decreasing subarray found.
  2. Iterate with i=0 (nums[i]=1):

    • Iterate j from 1 to the end of the array. Since nums[0] is less than all other elements (due to the increasing order at the beginning), no j will satisfy nums[i] > nums[j] for this round.
  3. Iterate with i=1 (nums[i]=2):

    • Similarly, nums[1] is less than all elements to its right, so again, no j will satisfy the condition for this i.
  4. Iterate with i=2 (nums[i]=12):

    • For j=3 (nums[j]=2): The condition is satisfied. Calculate tempLength = 2. Update maxLength = 2..
    • For j=4 (nums[j]=5): The condition is satisfied. Calculate tempLength = 3. Update maxLength = 3..
    • For j=5 (nums[j]=11): The condition is satisfied. Calculate tempLength = 4, update maxLength to 4.
    • For j=6 (nums[j]=13): The condition is not satisfied. No update to maxLength.
  5. Iterate with i=3 (nums[i]=2):

    • All subsequent j values for this i do not satisfy nums[i] > nums[j] because nums[i] is one of the smallest.
  6. Iterate with i=4 (nums[i]=5):

    • The process is similar to previous steps, with no updates to maxLength due to the condition not being met or finding shorter lengths than currently stored in maxLength.
  7. Iterate with i=5 (nums[i]=11):

    • For j=6 (nums[j]=13): The condition is not satisfied. No update to maxLength.
  8. Conclusion:

    • The iteration ends with maxLength = 4, representing the longest semi-decreasing subarray [12, 2, 5, 11].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

The nested loops iterate over each pair of elements in the array to check every possible subarray. Therefore, the time complexity is quadratic in the number of elements, n, in the input array.

Space Complexity:

Only a constant amount of extra space is used (variables for storing indices, lengths, and the maximum length found), so the space complexity is constant.

Optimized Solution

To solve this problem, we use a monotonic stack to efficiently find the maximum length of a semi-decreasing subarray. The idea is to track indices of elements in increasing order in the stack. Then, by traversing the array from right to left, we check where each element forms a semi-decreasing subarray. If an element is smaller than the element at the top of the stack, it means we have found a decreasing pattern, and we compute the subarray length.

This approach ensures that each index is pushed and popped at most once, leading to an time complexity. Instead of checking every subarray individually, which would be inefficient (² or worse), we leverage the stack to track potential subarray start points in a single pass, then efficiently compute the maximum subarray length in a second pass.

Step-by-Step Algorithm

  1. Initialize Required Variables:

    • Create an empty monotonic stack to store indices.
    • Store the length of the array in a variable n.
    • Initialize maxLength = 0 to keep track of the maximum subarray length.
  2. First Pass (Building the Stack - Left to Right):

    • Iterate through the array from index 0 to n - 1.
    • For each element:
      • If the stack is empty or the current element is greater than the element at the top index, push its index onto the stack.
      • This ensures the stack maintains indices in increasing order, which helps in identifying valid decreasing subarrays later.
  3. Second Pass (Finding Maximum Subarray - Right to Left):

    • Traverse the array from right to left (index n - 1 to 0).
    • For each element:
      • While the stack is not empty and the element at the top of the stack is greater than the current element, perform the following:
        • Compute the subarray length as (i - stack.peek() + 1).
        • Update maxLength if the computed subarray length is greater than its current value.
        • Pop the top element from the stack.
      • This ensures that we correctly determine the longest subarray where the first element is greater than the last, creating a valid semi-decreasing sequence.
  4. Return the Final Result:

    • After completing both passes, return the maximum subarray length stored in maxLength.

Algorithm Walkthrough

Input: [1, 2, 12, 2, 5, 11, 13]

1. Initialization

  • Input Array: [1, 2, 12, 2, 5, 11, 13]
  • Stack: [] (empty initially)
  • maxLength: 0
  • n: 7

2. First Pass – Building the Stack (Left to Right)

  • Iteration 1 (i = 0):
    • nums[0] = 1
    • Stack is empty → Push index 0.
    • Stack becomes: [0]
  • Iteration 2 (i = 1):
    • nums[1] = 2
    • Top index is 0 with nums[0] = 1 which is less than 2 → Push index 1.
    • Stack becomes: [0, 1]
  • Iteration 3 (i = 2):
    • nums[2] = 12
    • Top index is 1 with nums[1] = 2 (2 < 12) → Push index 2.
    • Stack becomes: [0, 1, 2]
  • Iteration 4 (i = 3):
    • nums[3] = 2
    • Top index is 2 with nums[2] = 12 (12 > 2) → Do not push.
    • Stack remains: [0, 1, 2]
  • Iteration 5 (i = 4):
    • nums[4] = 5
    • Top index is still 2 with nums[2] = 12 (12 > 5) → Do not push.
    • Stack remains: [0, 1, 2]
  • Iteration 6 (i = 5):
    • nums[5] = 11
    • Top index is still 2 with nums[2] = 12 (12 > 11) → Do not push.
    • Stack remains: [0, 1, 2]
  • Iteration 7 (i = 6):
    • nums[6] = 13
    • Top index is 2 with nums[2] = 12 (12 < 13) → Push index 6.
    • Stack becomes: [0, 1, 2, 6]

3. Second Pass – Calculating Maximum Subarray Length (Right to Left)

We now traverse from right to left. For each index i, we repeatedly check if the element at the top of the stack is greater than nums[i]. If so, we compute the subarray length using that index and then pop it off.

  • Iteration 1 (i = 6):
    • nums[6] = 13
    • Stack Top: Index 6 → nums[6] = 13 is not greater than nums[6] (they are equal).
    • No pop occurs.
    • Stack remains: [0, 1, 2, 6]
  • Iteration 2 (i = 5):
    • nums[5] = 11
    • Stack Top: Index 6 → nums[6] = 13 is greater than 11.
      • Calculate subarray length:
        • Use i (5) and stack top (6):
        • Length = i - stack.peek() + 1 = 5 - 6 + 1 = 0
      • Update: maxLength remains 0.
      • Pop index 6.
    • Stack becomes: [0, 1, 2]
    • While Loop Check Again:
      • Now, top is index 2 → nums[2] = 12 is greater than 11.
      • Calculate subarray length:
        • Length = 5 - 2 + 1 = 4
      • Update: maxLength becomes 4.
      • Pop index 2.
    • Stack becomes: [0, 1]
    • While Loop Ends:
      • Now, top is index 1 with nums[1] = 2 which is not greater than 11.
  • Iteration 3 (i = 4):
    • nums[4] = 5
    • Stack Top: Index 1 → nums[1] = 2 (2 is not greater than 5).
    • No pop occurs.
    • Stack remains: [0, 1]
  • Iteration 4 (i = 3):
    • nums[3] = 2
    • Stack Top: Index 1 → nums[1] = 2 is not greater than 2 (equal).
    • No pop occurs.
    • Stack remains: [0, 1]
  • Iteration 5 (i = 2):
    • nums[2] = 12
    • Stack Top: Index 1 → nums[1] = 2 is not greater than 12.
    • No pop occurs.
    • Stack remains: [0, 1]
  • Iteration 6 (i = 1):
    • nums[1] = 2
    • Stack Top: Index 1 itself, so nothing to compare.
    • No pop occurs.
    • Stack remains: [0, 1]
  • Iteration 7 (i = 0):
    • nums[0] = 1
    • Stack Top: Index 1 → nums[1] = 2 is greater than 1.
      • Calculate subarray length:
        • Length = 0 - 1 + 1 = 0
      • maxLength remains: 4.
      • Pop index 1.
    • Stack becomes: [0]
    • While Loop Check Again:
      • Now, top is index 0 → nums[0] = 1 is not greater than 1.
    • While Loop Ends.
    • Stack remains: [0]

4. Final Output

  • Final maxLength: 4
  • Thus, the maximum length of a semi-decreasing subarray for the array [1, 2, 12, 2, 5, 11, 13] is 4.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity Analysis

  1. First Pass (Building the Stack) →

    • We iterate over the array from left to right (i = 0 to n-1).
    • Each element is pushed onto the stack at most once.
    • Total operations: .
  2. Second Pass (Finding Maximum Subarray Length) →

    • We iterate over the array from right to left (i = n-1 to 0).
    • Each element is popped from the stack at most once.
    • Total operations: .

Since both passes run in independently, the overall time complexity is:
.

Space Complexity Analysis

  1. Stack Storage →
    • In the worst case, the stack may store all n indices (e.g., when elements are strictly increasing).
    • Space used by the stack: .
  2. Other Variables →
    • The algorithm uses a few integer variables (maxLength, n, loop counters), which require constant space.

Thus, the overall space complexity is due to the stack storage.

Maximum Length of Semi-Decreasing Subarrays (medium)
Minimum Area Rectangle (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Optimized Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis